package leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedList;

//[460]LFU 缓存
public class LfuCache460{
public static void main(String[] args) {
//   Solution solution = new LfuCache460().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
  class LFUCache {
    //	执行耗时:69 ms,击败了46.93% 的Java用户
    //	内存消耗:127.9 MB,击败了22.96% 的Java用户
      int minFreq,capacity,size;
      HashMap<Integer,Node> keyMap;
      // TODO: 2022/7/6  LinkedList 修改为自定义 node ,因为 删除node 是 O n, 自定义的话，删除 O1.
      HashMap<Integer, LinkedList<Node>> freqMap = new HashMap<>();

      public LFUCache(int capacity) {
          size = 0;
          this.minFreq = 0;
          this.capacity = capacity;
          keyMap = new HashMap<>(capacity);
      }

      public int get(int key) {
          if(capacity < 1) return -1;
          Node node = keyMap.get(key);
          if (node != null) {
              LinkedList<Node> nodes = freqMap.get(node.freq);
              nodes.remove(node);
              // 如果当前链表为空，且 当前 就是 minFreq 的list 更新 minFreq
              if (nodes.size() == 0 && minFreq == node.freq){
                  minFreq = minFreq +1;
              }
              int i = node.freq + 1;
              LinkedList<Node> nodelist = freqMap.get(i);
              if (nodelist == null){
                  nodelist = new LinkedList<Node>();
                  freqMap.put(i,nodelist);
              }
              node.freq = i;
              nodelist.offer(node);
          }
          return (node == null) ? -1:node.value;
      }

      public void put(int key, int value) {
          if(capacity < 1) return;
          if (keyMap.containsKey(key)){
              //update keyMap
              Node node = keyMap.get(key);
              node.value = value;

              // 如果当前链表为空，且 当前 就是 minFreq 的list 更新 minFreq
              LinkedList<Node> nodes = freqMap.get(node.freq);
              nodes.remove(node);
              if (nodes.size() == 0 && minFreq == node.freq){
                  minFreq = minFreq +1;
              }
              int i = node.freq + 1;
              LinkedList<Node> nodelist = freqMap.get(i);
              if (nodelist == null){
                  nodelist = new LinkedList<Node>();
                  freqMap.put(i,nodelist);
              }
              node.freq = i;
              nodelist.offer(node);
          }else {//not contain
              //> capacity
              if (size >= capacity){
                  Node poll = freqMap.get(minFreq).poll();
                  keyMap.remove(poll.key);//minFreq 为 new Node;
              }
              //add
              Node node = new Node(key, value, 1);
              keyMap.put(key,node);
              LinkedList<Node> nodelist = freqMap.get(1);
              if (nodelist == null){
                  nodelist = new LinkedList<Node>();
                  freqMap.put(1,nodelist);
              }
              nodelist.offer(node);//add 到尾部。
              size++;
              minFreq = 1;
          }
      }

      class Node{
          int key,value,freq;
          Node next,pri;
          public Node() {
              this(-1,-1,0);
          }

          public Node(int key, int value, int freq) {
              this.key = key;
              this.value = value;
              this.freq = freq;
          }
      }

      //TODO 待实现
      class DoubleEndList{
          Node head,tail;
          int size;

          public DoubleEndList() {
              head = new Node();
              tail = new Node();
              head.next = tail;
              tail.pri = head;
              size = 0;
          }

          public void remove(Node node){
              Node pri = node.pri;
              Node next = node.next;
              if (pri != null) {
                  pri.next = next;
              }
              if (next != null) {
                  next.pri = pri;
              }
              //验证 contain; ....
              size--;
          }

          //add last
          public void offer(Node node){
              tail.next = node;
              node.pri = tail;
              node.next = null;
              size++;
          }

          //poll first
          public Node poll(){
              Node temp = head;
              if (temp != null) {
                  head = temp.next;
              }
              return temp;
          }
      }
  }

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}